package chapter02;

import java.util.Stack;

public class MaximalRectangle85 {
    /**
     * 单调栈
     * 如果知道每一个[i][j]位置矩形的高度 通过单调栈方便计算
     * 求每一个位置的高度也就是求该位置到顶部连续1的数量
     * 本题与84不同在于84是一维 本题是二维
     * 行数作为外层循环遍历 为了方便计算 增加预处理数组colOne[i][j] i行j列到顶部有多少个连续1
     * 为了方便计算 预处理数组同样增加两列将矩形夹在中间
     */
    public int maximalRectangle(char[][] matrix){
        int row=matrix.length;
        int col=matrix[0].length;
        if(row<1||col<1){
            return 0;
        }
        int[][] colOne=new int[row][col+2]; //从上到下有多少个连续的1
        for(int j=0;j<col;j++){
            colOne[0][j+1]=matrix[0][j]=='0'?0:1;
        }
        for(int i=1;i<row;i++){
            for(int j=0;j<col;j++){
                colOne[i][j+1]=matrix[i][j]=='1'?colOne[i-1][j+1]+1:0;
            }
        }
        int res=0;
        col=colOne[0].length;
        for(int i=0;i<row;i++){
            Stack<Integer> stack=new Stack<>();
            int index=0;
            while(index<col){
                if(stack.isEmpty()||colOne[i][index]>=colOne[i][stack.peek()]){
                    stack.push(index++);
                    continue;
                }
                while (colOne[i][stack.peek()]>colOne[i][index]){
                    int height=colOne[i][stack.pop()];
                    res=Math.max(height*(index-stack.peek()-1),res);
                }
                stack.push(index++);
            }
        }
        return res;
    }

    //暴力超时
    public int maximalRectangle1(char[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        if(row<1||col<1){
            return 0;
        }
        int[][] rowOne=new int[row][col];
        int[][] colOne=new int[row][col];
        for(int i=0;i<row;i++){
            rowOne[i][col-1]=matrix[i][col-1]=='0'?0:1;
        }
        for(int j=0;j<col;j++){
            colOne[row-1][j]=matrix[row-1][j]=='0'?0:1;
        }
        for(int j=col-2;j>-1;j--){
            for(int i=0;i<row;i++){
                rowOne[i][j]=matrix[i][j]=='1'?rowOne[i][j+1]+1:0;
            }
        }
        for(int i=row-2;i>-1;i--){
            for(int j=0;j<col;j++){
                colOne[i][j]=matrix[i][j]=='1'?colOne[i+1][j]+1:0;
            }
        }
        int res=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                for(int i1=i;i1<row;i1++){
                    if(i1<i){
                        continue;
                    }
                    for(int j1=0;j1<col;j1++){
                        if(i1==i&&j1<j){
                            continue;
                        }
                        if(isValid(rowOne,colOne,i,j,i1,j1)){
                            res=Math.max(Math.abs(i1-i+1)*Math.abs(j1-j+1),res);
                        }
                    }
                }
            }
        }
        return res;
    }
    public boolean isValid(int[][] rowOne,int[][] colOne,int x,int y,int x1,int y1){
        for(int row=x;row<=x1;row++){
            if(rowOne[row][y]<Math.abs(y1-y+1)){
                return false;
            }
        }
        for(int col=y;col<=y1;col++){
            if(colOne[x][col]<Math.abs(x1-x+1)){
                return false;
            }
        }
        return true;
    }

//    public static void main(String[] args) {
//        char[][] chs={{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
//        System.out.println(new MaximalRectangle85().maximalRectangle(chs));
//    }
}
